package com.example.sorts13.sort;

/**
 * @description 计数排序（存储的都是非负整数）
 * @auther lijiewei
 * @date 2021/9/3 9:36
 */
public class CountingSort {

    /**
     * 计数排序（非负整数）
     * @param a 数组
     * @return
     * @author lijiewei
     * @date   2021/9/3 9:41
     */
    public static void countingSort(int[] a) {
        if (a.length <= 1) {
            return;
        }
        //查找数组中数据的最大值
        int max = a[0];
        for (int i = 1; i < a.length; i++) {
            if (max < a[i]) {
                max = a[i];
            }
        }
        //申请一个计数的数组,下标对应a数组的值
        int[] countArr = new int[max+1];
        for (int i = 0; i < a.length; i++) {
            countArr[a[i]]++;
        }
        //累加
        for (int i = 1; i < countArr.length; i++) {
            countArr[i] = countArr[i-1] + countArr[i];
        }
        //临时数组，存储排序后的结果
        int[] tmp = new int[a.length];
        for (int i = a.length-1; i >= 0; i--) {
            tmp[countArr[a[i]]-1] = a[i];
            countArr[a[i]]--;
        }
        //将结果拷贝到a数组
        for (int i = 0; i < tmp.length; i++) {
            a[i] = tmp[i];
        }
    }

}
